package com.leetcode.dynamic_programming;

/**
 * @author Dennis Li
 * @date 2020/7/20 10:40
 */
public class LongestCommonSubsequence_1143 {

    public int longestCommonSubsequence(String text1, String text2) {
        if (text1.equals(text2)) return text1.length();
        int high = text1.length(), width = text2.length();
        int[][] dp = new int[high + 1][width + 1];
        for (int i = 1; i <= high; i++) {
            for (int j = 1; j <= width; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1))
                    // 有相同，那么可以直接在基础上+1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    // 否则对比另外两个方向，即i前进一位，或者j前进一位，取其较大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[high][width];
    }

    static class Solution {
        public int longestCommonSubsequence(String text1, String text2) {
            if (text1.equals(text2)) return text1.length();
            int high = text1.length(), width = text2.length();
            int[][] dp = new int[high + 1][width + 1];
            for (int i = 1; i <= high; i++) {
                for (int j = 1; j <= width; j++) {
                    if (text1.charAt(i - 1) == text2.charAt(j - 1))
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    else
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
            return dp[high][width];
        }

        public int longestCommonSubsequence2(String text1, String text2) {
            if (text1.equals(text2)) return text1.length();

            int n = text1.length(), m = text2.length();
            int[] dp = new int[m + 1];

            for (int i = 1; i <= n; i++) {
                int pre = 0;
                for (int j = 1; j <= m; j++) {
                    // 注意压缩先提取最原始的dp[j]，他其实代表的是dp[i - 1][j]
                    int temp = dp[j];
                    if (text1.charAt(i - 1) == text2.charAt(j - 1))
                        dp[j] = pre + 1;
                    else
                        dp[j] = Math.max(dp[j], dp[j - 1]);
                    // 当进行下一轮循环之前进行如下变换，那么pre在一轮就变为了dp[i - 1][j - 1]
                    pre = temp;
                }
            }

            return dp[m];
        }



    }

}
